模拟赛题解/2025.9.19 模拟赛

T1-逆序对（inv）

题面

给定长度为 $n$ 的正整数序列 $a_{1\sim n}$。

$q$ 次询问，每次给出 $l,r$，求 $\max a_i+a_j$，满足 $l\leq i\leq j\leq r$，$a_i>a_j$，若不存在满足条件的 $i,j$ 则答案为 $0$。

为了减少输出量，你只需要输出 $q$ 次询问的答案的异或和。

$1\leq n,q\leq10^6,1\leq a_i\leq10^9,1\leq l\leq r\leq n$。

题解

不难发现只需关注每个 $a_i$ 与其前驱（最大的 $j$ 满足 $a_j < a_i$）。

证明：考虑按顺序的三个元素 $a_i,a_j,a_k$，其中 $i<j<k$，则 $a_j$ 不可能成为答案：

若 $a_j < a_k$，则前驱是 $a_i$；否则是 $a_k$。

记 $a_i$ 的前驱为 $p_i$，扫描 $a$ 从左到右，时刻维护每个 $a_i$ 的答案。只需要在 $p_i$ 移动的时候令对应位置取 $\min$ 即可。

容易使用树状数组等数据结构维护。

复杂度 $O(n \log n)$。

T2-一二三（yes）

题面

给你 $n$ 个数 $a_{1\sim n}$，其中 $a_i\in\{1,2,3\}$，每个数还有一个权值 $b_i$。

你可以进行如下操作若干次：

• 选择一段区间，满足这段区间的 $a_i$ 之和为 $4$ 或 $8$，将这段区间删除，并合并剩下的序列。

你希望剩下的数字的 $a_i$ 之和尽量小，如果有多种不同的方案，求出 $a_i$ 之和最小的条件下，$b_i$ 的最大可能和。

你需要输出对应的 $a_i$ 之和与 $b_i$ 之和。在有些子任务中，你要给出方案。

$o\in\{0,1\},1\leq n\leq3\times10^5,a_i\in\{1,2,3\},1\leq b_i\leq100$。

题解

考虑怎么判定是否能完全删除某个序列。

不妨先找出一些必要条件，显然 $\sum a_i\equiv0\bmod4$。在满足这个条件的基础下，不难发现如果 $a_i\leq 2$，则一定能完全删除，因此关键在于如何删除 $3$。

删除 的方法只有 3+1，3+3+2，3+5 三种，不难发现其中 $a_i\leq 2$ 的部分的和大于等于 $3$ 的个数。因此另外一个必要条件是 $\sum_{a_i\leq 2}a_i\geq\sum_{a_i=3}1$。可以构造性证明满足这两个必要条件就是充分的。

先考虑如何计算答案。记 $f_i$ 表示对于序列 $a_{1\sim i}$，如果最后留下了 $a_i$，那么最小的 $a$ 之和是多少。转移枚举 $j$ 满足区间 $j+1\sim i-1$ 可以被完全删除，求最小的 $f_j$。容易使用树状数组等数据结构加速。复杂度 $O(n\log n)$。

构造考虑先尽量删除所有 3+1 和 3+3+2，此时序列一定形如 $32\cdots232\cdots232\cdots23$，任意删除一段能删除的即可。

可以用一个栈维护现在的序列，如果栈顶的一段元素和为 $4$ 或 $8$，并且删掉这一段之后仍满足必要条件，就可以直接删掉。构造时间复杂度是 $O(n)$ 的。

T3-黑白树（tree）

题面

给你一棵 $n$ 个点的树，你要把每个节点黑白染色，定义它的丑陋程度为：

• 所有的连通块中，黑点和白点个数差的绝对值的最大值。

你希望它的丑陋程度尽量小。在这个问题中，你要解决三类问题：

1. 求出最小的丑陋程度。
2. 求出最小的丑陋程度，并且构造方案。
3. 你需要额外保证黑点和白点的个数之差不超过 $1$。求出满足这个要求的最小丑陋程度，并且构造方案。

$o\in\{1,2,3\},2\leq n\leq2\times10^5$。

题解

先找出答案的下界。

记叶子个数为 $k$，考虑所有非叶子与黑叶子构成的连通块，先删除所有黑叶子，再加入所有白叶子，值域变化为 $k$，因此答案至少是 $\lfloor\frac k2\rfloor$。

有经典结论是可以使用 $\lceil\frac k2\rceil$ 条可以相交的路径覆盖所有点，构造直接将叶子按 dfs 序编号，前一半和后一半按顺序匹配即可。那么可以将原树划分为 $\lceil\frac k2\rceil$ 个集合，每个集合是某条路径的子集。

把每个集合按照路径顺序黑白染色即可。一个连通块与一个集合的交集一定是连续的一段，因此黑白点个数之差不超过 $1$，总共 $\lceil\frac k2\rceil$ 个集合，因此最大黑白点数差不超过 $\lceil\frac k2\rceil$。

可以根据当前黑白点个数决定下一个集合是先染黑色还是先染白色，保证整体黑白点数差不超过 $1$。 集合划分时，不妨依次考虑 $\lceil\frac k2\rceil$ 条路径，将路径上未划分的点都划分进当前集合。容易使用并查集维护，或者找到所有叶子的重心后 dfs 维护。

复杂度 $O(n)$。

T4-抽卡牌（card）

题面

有 $n$ 种不同的卡牌，第 $i$ 种卡牌共有 $a_i$ 张，你希望获得 $b_i$ 张这种类型的卡牌。

初始所有卡牌都在卡池中，每一轮你会从卡池中的所有卡牌中随机抽取一张。设抽中的卡牌类型为 $x$，如果你已经有 $b_x$ 张该类型的卡牌，则你会将这张卡牌重新加入卡池，否则你会拿走这张牌，这张牌之后不会再进入卡池。

如果你手上每种卡牌的数量都达到了 $b_i$ 个的限制，游戏会立刻结束。求出游戏的期望轮数，对 $10^9+7$ 取模。

$1\leq n\leq2500,a_i\geq b_i\geq1,\sum a_i\leq5000$。

题解

考虑将这个无限过程改为有限的。若你抽出了一张牌 $x$ 时，已经有了 $b_x$ 张同类型牌，则视为将这张牌加入弃牌堆。若你手中已有 $x$ 张牌，弃牌堆中有 $y$ 张牌，则再抽出一张牌的期望时间为 $\frac{m-x}{m-x-y}$。

此时整个随机过程就可以被视为一个由 $a_i$ 生成的多重集排列，$\frac{m!}{\prod a_i!}$ 种排列都是等概率出现的。考虑计算 $f_{x,y}$ 表示 $(x,y)$ 这个状态在所有排列中出现的次数。

不妨枚举 $c_i$ 表示第 $i$ 种卡牌已经抽出了多少张，则根据多重集排列，方案数是：

$$\frac{(\sum c_i)!}{\prod c_i!}\times\frac{(m-\sum c_i)!}{\prod(a_i-c_i)!}$$

其中 $\sum c_i=x+y$，因此考虑在 dp 过程中计算上式分母乘积。

记 $f_{i,x,y}$ 表示前 $i$ 种卡牌中，此时手里有 $x$ 张，弃牌堆里有 $y$ 张。转移枚举 $c$，$x$ 加上 $\min(c,b_i)$，$y$ 加上 $\max(c-b_i,0)$。注意要扣掉满足所有 $c_i\geq b_i$ 的方案。复杂度 $O(m^3)$。

优化考虑 $\frac{m-x}{m-x-y}$ 中分母只与 $x+y$ 有关，在 dp 时可以直接记录 $x+y$，对分子的两项分别考虑。$m$ 这一项是简单的，最后乘 $m$ 即可，$x$ 这一项相当于在所有 $\min(c,b_i)$ 中选择了一个乘上去，dp 时多记录一维 01 即可。

复杂度 $O(m^2)$。